<html>
<head>
	<meta charset="UTF-8">
	<meta content="IE=edge" http-equiv="X-UA-Compatible">
	<meta content="initial-scale=1.0, maximum-scale=1.0, user-scalable=no, width=device-width" name="viewport">
	<title>4011：[HNOI2015]落忆枫音</title>
	<!-- css -->
	<link href="../css/base.min.css" rel="stylesheet">
	<link href="../css/project.min.css" rel="stylesheet">
	
	<!-- favicon -->
	<!-- ... -->
</head>
<body class="page-brand">
	<header class="header header-transparent header-waterfall ui-header">
		<ul class="nav nav-list pull-left">
			<li>
				<a data-toggle="menu" href="#menu">
					<span class="icon icon-lg">menu</span>
				</a>
			</li>
		</ul>
		<a class="header-logo header-affix-hide margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">[HNOI2015]落忆枫音</a>
		<span class="header-logo header-affix margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">[HNOI2015]落忆枫音</span>
	</header>
	<nav aria-hidden="true" class="menu" id="menu" tabindex="-1">
		<div class="menu-scroll">
			<div class="menu-content">
				<a class="menu-logo" href="../index.html">BZOJ离线题库</a>
				<ul class="nav">
					<li>
						<a class="waves-attach" data-toggle="collapse" href="#problems">题目</a>
						<ul class="menu-collapse collapse in" id="problems">
							<li>
								<a class="waves-attach" href="../index.html">主页</a>
							</li>
							<li>
								<a class="waves-attach" href="../list.html">题目列表</a>
							</li>
						</ul>
					</li>
					<li>
						<a class="collapsed waves-attach" data-toggle="collapse" href="#about">关于</a>
						<ul class="menu-collapse collapse" id="about">
							<li>
								<a class="waves-attach" href="../about.html">关于此项目</a>
							</li>
						</ul>
					</li>
					
				</ul>
			</div>
		</div>
	</nav>
	<main class="content">
		<div class="content-header ui-content-header">
			<div class="container">
				<h1 class="content-heading">
                [HNOI2015]落忆枫音                </h1>
                <p>时间限制：10s&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;  空间限制：512MB</p>			</div>
		</div>
		<div class="container">
			<section class="content-inner margin-top-no">
				<div class="row">
					<div class="col-lg-13 col-md-13">
						<div class="card margin-bottom-no">
							<div class="card-main">
								<div class="card-inner">
									
                                <h3>题目描述</h3><p><p>「恒逸，你相信灵魂的存在吗？」&nbsp;</p>
<div>郭恒逸和姚枫茜漫步在枫音乡的街道上。望着漫天飞舞的红枫，枫茜突然问出</div>
<div>这样一个问题。&nbsp;</div>
<div>「相信吧。不然我们是什么，一团肉吗？要不是有灵魂&hellip;&hellip;我们也不可能再见</div>
<div>到你姐姐吧。」&nbsp;</div>
<div>恒逸给出了一个略微无厘头的回答。枫茜听后笑了笑。&nbsp;</div>
<div>「那你仔细观察过枫叶吗？」&nbsp;</div>
<div>说罢，枫茜伸手，接住了一片飘落的枫叶。&nbsp;</div>
<div>「其实每一片枫叶都是有灵魂的。你看，枫叶上不是有这么多脉络吗？我听说，</div>
<div>枫叶上有一些特殊的位置，就和人的穴位一样。脉络都是连接在这些穴位之间的。</div>
<div>枫树的灵魂流过每片枫叶的根部，沿着这些脉络，慢慢漫进穴位，沁入整片枫叶。</div>
<div>也是因为这个原因，脉络才都是单向的，灵魂可不能倒着溜回来呢。」&nbsp;</div>
<div>恒逸似懂非懂地点了点头。枫茜接着说了下去。&nbsp;</div>
<div>「正是因为有了灵魂，每片枫叶才会与众不同。也正是因为有了灵魂，每片枫</div>
<div>叶也都神似其源本的枫树，就连脉络也形成了一棵树的样子。但如果仔细看的话，</div>
<div>会发现，在脉络树之外，还存在其它的非常细的脉络。虽然这些脉络并不在树上，</div>
<div>但他们的方向也同样顺着灵魂流淌的方向，绝不会出现可能使灵魂倒流的回路。」 &nbsp;</div>
<div>恒逸好像突然想到了什么。&nbsp;</div>
<div>「那这些脉络岂不是可以取代已有的脉络，出现在脉络树上？」&nbsp;</div>
<div>枫茜闭上了眼睛。&nbsp;</div>
<div>「是啊，就是这样。脉络树并不是唯一的。只要有一些微小的偏差，脉络树就</div>
<div>可能差之万里，哪怕是在这同一片枫叶上。就像我们的故事，结局也不是唯一的。</div>
<div>只要改变一个小小的选项，故事流程可能就会被彻底扭转。」&nbsp;</div>
<div>「真是深奥啊&hellip;&hellip;」&nbsp;</div>
<div>恒逸盯着这片红枫，若有所思地说。枫茜继续说道。&nbsp;</div>
<div>「还不止如此呢。所有的脉络都不会永恒存在，也不会永恒消失。不管是脉络</div>
<div>树上的脉络，还是之外的细小脉络，都是如此。存在的脉络可能断开消失，消失的</div>
<div>脉络也可能再次连接。万物皆处在永恒的变化之中，人与人之间的羁绊也是。或许</div>
<div>有一天，我们与大家的羁绊也会如同脉络一样，被无情地斩断。或许我们也终将成</div>
<div>为&ldquo;枫音乡的过客&rdquo;。或许这一切都会是必然，是枫树的灵魂所决定的&hellip;&hellip;」&nbsp;</div>
<div>枫茜的眼角泛起了几滴晶莹剔透的泪珠。恒逸看着这样的枫茜，将她抱入怀中。 &nbsp;</div>
<div>「别这样想，枫茜。就算脉络断开，也有可能还会有新的脉络树，也还会与枫</div>
<div>树的根相连。这样的话，我们的羁绊仍然存在，只是稍微绕了一些远路而已。无论</div>
<div>如何，我都不会离开你的。因为你是我穷尽一生所寻找的，我的真恋啊！」&nbsp;</div>
<div>两人的目光对上了。枫茜幸福地笑了，把头埋进了恒逸的怀抱。从远方山上的</div>
<div>枫林中，传来了枫的声音。&nbsp;</div>
<div>【问题描述】&nbsp;</div>
<div>不妨假设枫叶上有 n个穴位，穴位的编号为 1 ~ &nbsp;n。有若干条有向的脉络连接</div>
<div>着这些穴位。穴位和脉络组成一个有向无环图&mdash;&mdash;称之为脉络图（例如图 1），穴</div>
<div>位的编号使得穴位 1 没有从其他穴位连向它的脉络，即穴位 1 只有连出去的脉络；</div>
<div>由上面的故事可知，这个有向无环图存在一个树形子图，它是以穴位 1为根的包含</div>
<div>全部n个穴位的一棵树&mdash;&mdash;称之为脉络树（例如图 2和图 3给出的树都是图1给出</div>
<div>的脉络图的子图）；值得注意的是，脉络图中的脉络树方案可能有多种可能性，例</div>
<div>如图2和图 3就是图 1给出的脉络图的两个脉络树方案。&nbsp;</div>
<div>&nbsp; &nbsp; &nbsp; &nbsp;<img src="../file/4011_0.png" width="636" height="214" alt="" /></div>
<div>脉络树的形式化定义为：以穴位 r 为根的脉络树由枫叶上全部 n个穴位以及 n</div>
<div>- &nbsp;1 条脉络组成，脉络树里没有环，亦不存在从一个穴位连向自身的脉络，且对于</div>
<div>枫叶上的每个穴位 s，都存在一条唯一的包含于脉络树内的脉络路径，使得从穴位</div>
<div>r 出发沿着这条路径可以到达穴位 s。&nbsp;</div>
<div>现在向脉络图添加一条与已有脉络不同的脉络（注意：连接 2个穴位但方向不</div>
<div>同的脉络是不同的脉络，例如从穴位3到4的脉络与从4到3的脉络是不同的脉络，</div>
<div>因此，图 1 中不能添加从 3 到 4 的脉络，但可添加从 4 到 3 的脉络），这条新脉络</div>
<div>可以是从一个穴位连向自身的（例如，图 1 中可添加从 4 到 4 的脉络）。原脉络图</div>
<div>添加这条新脉络后得到的新脉络图可能会出现脉络构成的环。&nbsp;</div>
<div>请你求出添加了这一条脉络之后的新脉络图的以穴位 1 为根的脉络树方案数。</div>
<div>由于方案可能有太多太多，请输出方案数对 1,000,000,007 取模得到的结果。&nbsp;</div></p><hr/><h3>输入格式</h3><p><p>输入文件的第一行包含四个整数 n、m、x和y，依次代表枫叶上的穴位数、脉</p>
<div>络数，以及要添加的脉络是从穴位 x连向穴位y的。&nbsp;</div>
<div>接下来 m行，每行两个整数，由空格隔开，代表一条脉络。第 i 行的两个整数</div>
<div>为ui和vi，代表第 i 条脉络是从穴位 ui连向穴位vi的。&nbsp;</div></p><hr/><h3>输出格式</h3><p><p>&nbsp;输出一行，为添加了从穴位 x连向穴位 y的脉络后，枫叶上以穴位 1 为根的脉</p>
<div>络树的方案数对 1,000,000,007取模得到的结果。&nbsp;</div></p><hr/><h3>样例输入</h3><pre>4 4 4 3 
1 2 
1 3 
2 4 
3 2 </pre><hr/><h3>样例输出</h3><pre>3</pre><hr/><h3>提示</h3><p><p>&nbsp;对于所有测试数据，1 &lt;= n &lt;= 100000，n - 1 &lt;= m &lt;= min(200000, n(n &ndash; 1) / 2)，&nbsp;</p>
<div>1 &lt;= x, y, ui, vi &lt;= n。</div>
<div></div></p><hr/><h3>题目来源</h3><p>没有写明来源</p>
								</div>
							</div>
						</div>
					</div>
				</div>
				
				
			</section>
		</div>
	</main>

	<div class="fbtn-container">
		<div class="fbtn-inner">
			<a class="fbtn fbtn-lg fbtn-brand-accent waves-attach waves-circle waves-light waves-effect" data-toggle="dropdown" aria-expanded="true"><span class="fbtn-text fbtn-text-left">Menu</span><span class="fbtn-ori icon">apps</span><span class="fbtn-sub icon">close</span></a>
			<div class="fbtn-dropup">
				<a class="fbtn fbtn-brand waves-attach waves-circle waves-light waves-effect" href="../list.html" target="_self"><span class="fbtn-text fbtn-text-left">题目列表</span><span class="icon">menu</span></a>
				<a class="fbtn fbtn-green waves-attach waves-circle waves-effect" href="../index.html" target="_self"><span class="fbtn-text fbtn-text-left">返回主页</span><span class="icon">home</span></a>
				<a class="fbtn waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/submitpage.php?id=4011" target="_blank"><span class="fbtn-text fbtn-text-left">提交代码</span><span class="icon">send</span></a>
				<a class="fbtn fbtn-orange waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/wttl/wttl.php?pid=4011" target="_blank"><span class="fbtn-text fbtn-text-left">试题讨论</span><span class="icon">chat</span></a>
				
			</div>
		</div>
	</div>

	<!-- js -->
	<script src="../js/jquery.min.js"></script>
	<script src="../js/base.min.js"></script>
	<script src="../js/project.min.js"></script>
</body>
</html>